package forth

/*
	把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，
	输出旋转数组的最小元素。例如，数组[3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

	示例 1：
	输入：[3,4,5,1,2]
	输出：1

	示例 2：
	输入：[2,2,2,0,1]
	输出：0
	注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/*
	取旋转后的数组中间元素mid
	如果mid大于数组最右边元素hight，说明最小值在mid右边、此时只需要再考虑[mid+1...hight]中的数据
	如果mid小于hight、则mid有可能是最小值、也有可能比最小值大、此时只需要再考虑[l...mid]中的数据
	如果mid等于hight、无法判断最小值是在mid的左边还是右边、但此时可以不再考虑hight这个元素、因为数组中还有相等的元素mid、不会丢数据
*/
func minArray(numbers []int) int {
	l, r := 0, len(numbers)-1

	for l < r {
		mid := (l + r) / 2
		if numbers[mid] > numbers[r] {
			l = mid + 1
		} else if numbers[mid] == numbers[r] {
			r--
		} else {
			r = mid
		}
	}
	return numbers[l]
}
